//
// Created by Administrator on 2021/11/13.
//

#include <cstdio>
#include <cstdlib>
#include <stack>
/*#include "顺序栈.cpp"*/

#define MaxSize 100//定义最大个数
#define ElemType int

/*struct ElemType {
    int value;
};*/

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;//左孩子，右孩子指针
    struct BiTNode *parent;//父节点指针(方便寻找父结点，考研一般不爱考)
} BiTNode, *BiTree;

void Initializing_A_Binary_Tree() {
    /*定义一课空树*/
    BiTree root = NULL;
    /*插入根节点*/
    root = (BiTree) malloc(sizeof(BiTNode));//申请根节点
    root->data = {1};
    root->lchild = NULL;
    root->rchild = NULL;
}

void Left_Child_Inserted_Into_New_Node(BiTree &root) {
    //插入新结点
    BiTNode *p = (BiTNode *) malloc(sizeof(BiTNode));
    p->data = {2};
    p->lchild = NULL;
    p->rchild = NULL;
    root->lchild = p;//作为根节点的左孩子
}

void visit(BiTree T) {
    printf("访问结点：%d\n", T->data);
}

/*先序遍历*/
void PreOrder(BiTree T) {
    if (T) {
        visit(T);//访问根结点
        PreOrder(T->lchild);//递归遍历左子树
        PreOrder(T->rchild);//递归遍历右子树
    }
}

/*中序遍历*/
void InOrder(BiTree T) {
    if (T) {
        InOrder(T->lchild);//递归遍历左子树
        visit(T);//访问根结点
        InOrder(T->rchild);//递归遍历右子树
    }
}

/*后序遍历*/
void PostOrder(BiTree T) {
    if (T) {
        PostOrder(T->lchild);//递归遍历左子树
        PostOrder(T->rchild);//递归遍历右子树
        visit(T);//访问根结点
    }
}
/*先序遍历( PreOrder）的操作过程如下:
 * 1.若二叉树为空，则什么也不做;
 * 2.若二叉树非空:
 * ①访问根结点;(第1次路过时访问结点)
 * ②先序遍历左子树;
 * ③先序遍历右子树。
 * 脑补空结点，从根节点出发，画一条路:
 * 如果左边还有没走的路，优先往左边走走到路的尽头（空结点）就往回走
 * 如果左边没路了，就往右边走
 * 如果左、右都没路了，则往上面走
 * 先序遍历--第1次路过时访问结点
 * 其他遍历类似*/

/*求二叉树的深度*/
int treeDepth(BiTree T) {
    if (T == NULL) {
        return 0;
    } else {
        int l = treeDepth(T->lchild);
        int r = treeDepth(T->rchild);
        //树的深度=Max(左子树深度，右子树深度)+1
        return l > r ? l + 1 : r + 1;
    }
}

typedef struct {
    BiTNode *data[MaxSize];
    int top;
} TStack;

/*初始化栈*/
void InitStack(TStack &S) {
    S.top = -1;//初始化栈顶指针
}

/*判断栈空*/
bool StackEmpty(TStack S) {
    return S.top == -1;
}

/*新元素入栈*/
bool Push(TStack &S, BiTNode *x) {
    if (S.top == MaxSize - 1) {
        return false;//栈满，报错
    }
    S.top = S.top + 1;//指针先加1
    S.data[S.top] = x;//新元素入栈
    return true;
}

/*出栈操作*/
bool Pop(TStack &S, BiTree &x) {
    if (S.top == -1) {
        return false;//栈空，报错
    }
    x = S.data[S.top--];//栈顶元素先出栈s.top = s.top - 1;/指针再减1
    return true;
}

/*读栈顶元素*/
bool GetTop(TStack S, BiTree &x) {
    if (S.top == -1) {
        return false; //栈空，报错
    }
    x = S.data[S.top];//x记录栈顶元素
    return true;
}

/*中序遍历的非递归算法*/
void Non_recursive_Algorithm_For_InOrder(BiTree T) {
    TStack S;//定义一个栈
    InitStack(S);//初始化栈
    BiTree p = T;//p是遍历指针
    while (p || !StackEmpty(S)) {
        //栈不空，或者，p不空，继续
        if (p) {
            //根指针不空
            //visit(p);//访问根节点前序
            Push(S, p);
            p = p->lchild;//向左走，遍历左子树
        } else {
            //根指针=空，
            Pop(S, p);//退栈
            visit(p);//访问根节点
            p = p->rchild;//向右走，遍历右子树
        }
    }
}

/*后序遍历的非递归算法*/
void Non_recursive_Algorithm_For_PostOrder(BiTree T) {
    TStack S;//定义一个栈
    InitStack(S);//初始化栈
    BiTNode *p = T;//p是遍历指针
    BiTree r = NULL;//辅助指针，指向最近访问过的结点
    while (p || !StackEmpty(S)) {
        if (p) {
            //只要左子树存在就一直往下走，直到最左边
            Push(S, p);
            p = p->lchild;
        } else {
            GetTop(S, p);//读取栈顶结点
            if (p->rchild && p->rchild != r) {
                //（从左子树返回来）右子树存在&&未被访问过
                p = p->rchild;//向右走
                Push(S, p);//入栈
                p = p->lchild;//向左走
            } else {
                //（右子树全部从栈中弹出）弹出结点，并访问
                Pop(S, p);//出栈
                visit(p);//访问
                r = p;//记录最近访问的节点
                p = NULL;//访问完后，重置p指针
            }
        }
    }
}

/* 二叉树的层序遍历：
 * 算法思想:
 * ①初始化一个辅助队列
 * ②根结点入队
 * ③若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话)
 * ④重复③直至队列为空 */

typedef struct LinkNode {
    BiTNode *data;
    struct LinkNode *next;
    int length;//记录链表长度
} LinkNode;

typedef struct {
    LinkNode *front, *rear;//队列的队头和队尾指针
} LinkQueue;

//初始化队列(不带头结点)
void InitQueue(LinkQueue &Q) {
//初始时front、rear 都指向NULL
    Q.front = NULL;
    Q.rear = NULL;
}

/*新元素入队(不带头结点)
 * 在链尾加入新节点*/
void EnQueue(LinkQueue &Q, BiTNode *x) {
    LinkNode *S = (LinkNode *) malloc(sizeof(LinkNode));
    S->data = x;
    S->next = NULL;
    if (Q.front == NULL) {
        //在空队列中插入第一个元素
        Q.front = S;//修改队头队尾指针(首次：新节点成为头结点)
        Q.rear = S;//新节点成为尾结点
    } else {
        Q.rear->next = S;//新结点插入到rear结点之后
        Q.rear = S;//修改rear 指针（新节点成为尾结点）
    }
}

/*判断队列是否为空(不带头结点)
 * 925*/
bool IsEmpty(LinkQueue Q) {
    return Q.front == NULL;//注意判空条件
}

/*队头元素出队(不带头结点)*/
bool DeQueue(LinkQueue &Q, BiTNode *&x) {
    if (Q.front == NULL) {
        return false; //空队
    }
    LinkNode *p = Q.front;//p指向此次出队的结点（找到第一个节点）
    x = p->data;//用变量x返回队头元素
    Q.front = p->next;//修改front 指针（头指针指向第二个节点）
    if (Q.rear == p) {
        //此次是最后一个结点出队
        Q.front = NULL;//front指向NULL
        Q.rear = NULL;//rear指向NULL
    }
    free(p);//释放结点空间
    return true;
}

/*层序遍历*/
void LevelOrder(BiTree T) {
    LinkQueue Q;
    InitQueue(Q);//初始化辅助队列
    BiTree p;
    EnQueue(Q, T);//将根结点入队
    while (!IsEmpty(Q)) {
        //队列不空则循环
        DeQueue(Q, p);//队头结点出队
        visit(p);//访问出队结点
        if (p->lchild != NULL) {
            EnQueue(Q, p->lchild);//左孩子入队
        }
        if (p->rchild != NULL) {
            EnQueue(Q, p->rchild);//右孩子入队
        }
    }
}